package org.example.myleet.p456;

public class Solution {
    /**
     * 2 ms
     * 利用单调栈维护作为2的候选数字
     */
    public boolean find132pattern(int[] nums) {
        int n = nums.length;
        if (n < 3) {
            return false;
        }
        //作为2的有效的最大的数字
        int max2 = Integer.MIN_VALUE;
        //si为栈指针，si与candidate2共同作为栈的功能
        int si = 0;
        int[] candidate2 = new int[n];
        //初始化，最后一个数作为2的候选数字
        candidate2[si++] = nums[n-1];
        for (int i=n-2; i>=0; --i) {
            if (nums[i] < max2) {
                //如果nums[i]比2的有效的最大的数字更小，说明找到一种子序列
                return true;
            }
            //更新作为2的有效的最大的数字，将nums[i]看作3，则栈顶比3模式数字（nums[i]）小的数都可以成为2的候选数字，弹出以更新2的有效的最大的数字
            while (si > 0 && nums[i] > candidate2[si-1]) {
                max2 = Math.max(max2, candidate2[--si]);
            }
            if (nums[i] > max2) {
                //nums[i]入栈，成为2的候选数字，如果小于max2就不用入栈了，因为即使被弹出来也更新不了max2
                candidate2[si++] = nums[i];
            }
        }
        return false;
    }
}
